package developer.算法.普通数组.缺失的一个正数;

/**
 * @author zhangyongkang
 * @time 2025/3/18 16:49
 * @description 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * <p>
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,0]
 * 输出：3
 * 解释：范围 [1,2] 中的数字都在数组中。
 * 示例 2：
 * <p>
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 * 解释：1 在数组中，但 2 没有。
 * 示例 3：
 * <p>
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 * 解释：最小的正数 1 没有出现。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 105
 * -231 <= nums[i] <= 231 - 1
 */
public class Queshidediyigezhengshu {

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{3, 4, -1, 1}));
        System.out.println(firstMissingPositive(new int[]{1, 2, 0}));
        System.out.println(firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
    }

    //核心思想 对数据进行打标 巧用 数字当hash表 如果当前的数据存在 那么对应的数字数据标记为负数
    //另外要对负数做额外处理

    public static int firstMissingPositive(int[] nums) {
        //核心的思想是对进行打标记 判定当前的数据是否存在
        /**
         * 如果空间复杂度为O(n)情况下
         * 解题思路
         * Set<Integer> value = new HashSet<>();
         *for(int i =1;i++){
         *     if(!value.cotains(i){
         *         return i;
         *     }
         *
         *}
         * 下面通过打标记的方法 巧用数组的索引 当作hash表
         */
        int oom = nums.length + 1;
        //将小于0的数标记为 nums.length + 1 最小的数可能是 nums.length + 1
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (num <= 0) {
                nums[i] = oom;
            }
        }
        //将小于 nums.length + 1
        //这一个循环结束后，如果当前索引+1 的值存在，那么当前索引的值就会为 负数
        for (int i = 0; i < nums.length; i++) {
            int num = Math.abs(nums[i]);
            if (num < oom && num > 0) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (num > 0) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
    /**
     * 我们对数组进行遍历，对于遍历到的数 x，如果它在 [1,N] 的范围内
     * ，那么就将数组中的第 x−1 个位置
     * （注意：数组下标从 0 开始）打上「标记」。
     * 在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。
     *
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/first-missing-positive/solutions/304743/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     *
     * 我们将数组中所有小于等于 0 的数修改为 N+1；
     *
     * 我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣，
     * 其中 ∣∣ 为绝对值符号。如果 ∣x∣∈[1,N]，那么我们给数组中的第 ∣x∣−1 个位置的数添加一个负号。
     * 注意如果它已经有负号，不需要重复添加；
     *
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/first-missing-positive/solutions/304743/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

}
